package top.fengleifeng.question;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author : fengelfeing
 * @version V1.0
 * @Project: leetcode-test
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年11月02日5:56 下午
 */
public class Num133克隆图 {

    /*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
    static class Node {

        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    class Solution {

        public Node cloneGraph(Node node) {
            if (node == null) {
                return null;
            }
            Map<Integer, Node> map = new HashMap<>();
            Node result = check(node, map);
            return result;
        }

        private Node check(Node node, Map<Integer, Node> map) {
            if (map.get(node.val) != null) {
                return map.get(node.val);
            }
            Node result = new Node(node.val);
            map.put(node.val, result);
            result.neighbors = new LinkedList<>();
            if (node.neighbors != null && node.neighbors.size() > 0) {
                for (Node one : node.neighbors) {
                    Node check = check(one, map);
                    result.neighbors.add(check);
                }
            }
            return result;
        }
    }

    public static void main(String[] args) throws Exception {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node.neighbors.add(node2);
        node.neighbors.add(node4);

        node2.neighbors.add(node);
        node2.neighbors.add(node3);

        node3.neighbors.add(node2);
        node3.neighbors.add(node4);

        node4.neighbors.add(node);
        node4.neighbors.add(node3);
        Node node1 = new Num133克隆图().new Solution().cloneGraph(node);

    }

}
